package huawei;

import java.util.HashMap;
import java.util.Map;

/**
 * @author pengfei.hpf
 * @date 2020/3/26
 * @verdion 1.0.0
 */
public class MinimumLengthEncoding {
    public int minimumLengthEncoding(String[] words) {
        if(words == null || words.length == 0){
            return 0;
        }
        StringBuilder builder = new StringBuilder();
        int[] index = new int[words.length];
        int cur = 0;
        int i = 0;
        for(String str: words){
            index[i] = cur;
            builder.append(str);
            builder.append("#");
            cur += str.length() + 1;
            i ++;
        }
        int ans = builder.length();
        i = 0;
        for(String str: words){
            int find = builder.indexOf(str);
            int findLast = builder.lastIndexOf(str);
            if((find > 0 && find < index[i]) || (findLast != find && findLast > index[i])){
                if((find != index[i] && builder.charAt(find + str.length()) == '#') || (findLast != index[i] &&builder.charAt(findLast + str.length()) =='#')){
                    ans -= (str.length() + 1);
                }

            }
            i ++;
        }
        return ans;
    }

    public int minimumLengthEncodingII(String[] words){
        if(words == null || words.length == 0){
            return 0;
        }
        Map<Trie, Integer> map = new HashMap<>();
        Trie root = new Trie();
        int i = 0;
        for(String str: words){
            Trie cur = root;
            //TODO: 字符串处理, 可以用字符串倒置前缀树
            for(int j = str.length() -1; j >= 0; j --){
                cur = cur.get(str.charAt(j));
            }
            map.put(cur, i);
            i++;
        }
        int ans = 0;
        for(Map.Entry<Trie, Integer> entry : map.entrySet()){
            Trie node = entry.getKey();
            if(node.count == 0){
                ans += words[entry.getValue()].length() + 1;
            }
        }
        return ans;
    }

    class Trie{
        Trie[] childs = new Trie[26];
        int count = 0;

        Trie get(char c){
            if(childs[c - 'a'] == null){
                childs[c - 'a'] = new Trie();
                count ++;
            }
            return  childs[c - 'a'];
        }
    }
    public static void main(String[] args){
        System.out.println(new MinimumLengthEncoding().minimumLengthEncoding(new String[]{"me", "im", "time"}));
    }
}
